//
// Created by user on 2022/4/26.
//
/*
 二维费用背包问题：(有两种代价)
     有n种物品，每种物品只有1件，选择一种物品必须付出两种代价
     第i种物品第一种代价值是W[i]，第二种代价值是g[i]，物品的价值是v[i]
     对于每种代价部有一个可付出的最大值（两种背包容量）W和G

     问怎样选择物品可以得到最大的价值。
 */
#include <vector>
#include <algorithm>
using namespace std;
class Knapsack_2D{
public:
    int knapsack2d(vector<int> &w, vector<int> &g, int W, int G, vector<int> &v){

        vector<vector<int>> dp(W+1, vector<int>(G+1));

        //初始化

        //状态转移
        for (int i = 0; i < w.size(); i++) {
            for (int j = W; j >=w[i] ; j--) {
                for (int k = G; k >=g[i] ; k--) {
                    dp[j][k] = max(dp[j][k], dp[j-w[i]][k-g[i]]+v[i]);
                }
            }
        }
        return dp[W][G];
    }

};

